\documentclass[hyperref,UTF8]{ctexart}
\usepackage{hyperref}

\usepackage{fancyhdr}
\pagestyle{fancy}
\usepackage{enumerate}
\usepackage{geometry}
\geometry{a4paper,scale=0.72}
\setlength\headwidth{\textwidth}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{mathtools}
\ctexset{section={format={\Large\bfseries}}}

\title{Work1: 1.8.1 Theoretical questions}


\author{邵盛栋 \\ 信息与计算科学 3200103951}

\begin{document}
	\maketitle
	\section*{习题解答}
	\begin{enumerate}[I]
		\item 解：
		\begin{itemize}
			\item 第n步的间隔宽度是$ \dfrac{1}{2^{n-1}} $;
			\item 第n步根r和区间最大可能距离是$ \dfrac{1}{2^{n}} $.
		\end{itemize}
		\item 
			\begin{proof}
				由上题已知,第n步根r和区间最大可能距离是$ \dfrac{1}{2^{n}} $,则第n步时的误差满足：
				\[\Delta x\leq \dfrac{b_{0}-a_{0}}{2^{n+1}} \]
				而相对误差$ \dfrac{\Delta x}{x}\leq\epsilon $,则n需满足$ \dfrac{b_{0}-a_{0}}{2^{n+1}x}\leq\epsilon $.\\
				由条件$ n\geq\dfrac{\log(b_{0}-a_{0})-\log\epsilon-\log a_{0}}{\log2}-1 $可得:\[\dfrac{b_{0}-a_{0}}{2^{n+1}x}\leq\dfrac{a_{0}\epsilon}{x}\leq\epsilon\]
				得证
			\end{proof}
		\item 解：多项式方程：$ p(x)=4x^{3}-2x^{2}+3 $,以$ x_{0}=-1 $为起点,进行$ x_{n+1}=x_{n}-\dfrac{p(x)}{p'(x)} $
		\begin{table*}[ht]
			\centering
			\begin{tabular}{|c|c|c|c|}
				\hline
				n&$x_{n}$&$p(x_{n})$&$ p'(x_{n}) $\\
				\hline
				0&-1&-3&16\\
				\hline
				1&-0.8125&-0.4658&11.1719\\
				\hline
				2&-0.7708&-0.0201&10.2128\\
				\hline
				3&-0.7688&-0.0003&10.1678\\
				\hline
				4&-0.7688&-0.0003&10.1678\\
				\hline
			\end{tabular}
		\end{table*}
	\newpage
		\item 解：由于$ e_{n} $是牛顿法在第n步时的误差，则$ e_{n}=f(x_{n}) $.\\
		根据泰勒展开公式:
		\[f(x)=f(x_{n})+f'(x_{n})(x-x_{n})+o(x-x_{n})\]
		其中$ x-x_{n}\to0 $,则$ o(x-x_{n}) $是$ x-x_{n} $的无穷小量.\\
		令$ x=x_{n+1} $(在n足够大时$ x_{n+1}-x_{n}\to0 $),
		则$ f(x_{n+1})=f(x_{n})+f'(x_{n})(x_{n+1}-x_{n}) $\\
		由题意知$ x_{n+1}=x_{n}-\dfrac{f(x_{n})}{f'(x_{0})} $,则$ x_{n+1}-x_{n}=-\dfrac{f(x_{n})}{f'(x_{0})} $,代入上式：
		\[f(x_{n+1})=(1-\dfrac{f'(x_{n})}{f'(x_{0})})f(x_{n})\]
		即$ e_{n+1}=(1-\dfrac{f'(x_{n})}{f'(x_{0})})e_{n} $,
		所以$ s=1 $, $ C=1-\dfrac{f'(x_{n})}{f'(x_{0})} $.
		
		\item 解：所给迭代为$ x_{n+1}=\tan^{-1}x_{n} $,即$ \tan x_{n+1}=x_{n} $.\\
		当$ x_{0}=0 $时, $ x_{n}=0,\forall n $,迭代显然收敛.\\
		不妨假设$ x_{0}\in(0,\dfrac{\pi}{2}) $,由于存在结论$ x\textless\tan x,x\in(0,\dfrac{\pi}{2}) $,则
		\[x_{n+1}\textless\tan x_{n+1}=x_{n}\]
		即数列$ {x_{n}} $为单调递减数列，且每项都大于0.假设该数列的极限$ \lim\limits_{n\to +\infty}x_{n}=x'>0 $\\
		对于$ x' $, $ x''\textless\tan x''=x' $,矛盾！所以$ \lim\limits_{n\to +\infty}x_{n}=0 $,迭代收敛.\\
		若$ x_{0}\in(-\dfrac{\pi}{2},0) $,同理可证得迭代收敛.
		
		\item 
			\begin{proof}
				由提示得,序列可转化为如下数组:
				\[x_{1}=\dfrac{1}{p},x_{2}=\dfrac{1}{p+\frac{1}{p}},x_{3}=\dfrac{1}{p+\frac{1}{p+\frac{1}{p}}},\dots\]
				可以发现,$ x_{n+1}=\dfrac{1}{p+x_{n}} $,可构造函数$ f(x)=\dfrac{1}{p+x} $.\\
				引理: $ x^{*} $是$ x_{n+1}=f(x_{n}) $的一个不动点,如果$ |f'(x^{*})|<1 $,则$ x^{*} $是可收敛的.\\
				证明: $\exists M>0$,使得$ |f'(x^{*})|<M<1 $.则$\exists \delta>0$,当$ x\in I=(x^{*}-\delta,x^{*}+\delta) $时,
				\[|f'(x)|\leq M<1,x\in I\]
				于是当$ x_{0}\in I $时
				\[|x_{1}-x^{*}|=|f(x_{0})-f(x^{*})|\]
				由中值定理，$\exists \zeta\in(x_{0},x^{*})/(x^{*},x_{0})$,使得$ |x_{1}-x^{*}|=|f'(\zeta)||x_{0}-x^{*}| $,则
				\[|x_{1}-x^{*}|=|f'(\zeta)||x_{0}-x^{*}|\leq M|x_{0}-x^{*}|\]
				即
				\[|x_{1}-x^{*}|\leq M|x_{0}-x^{*}|\]
				以此类推, $ x_{n}\in(x_{0},x^{*})/(x^{*},x_{0}) $,有
				\[ |x_{n}-x^{*}|\leq M^{n}|x_{0}-x^{*}|\to0,n\to\infty \]
				于是
				\[\lim\limits_{n\to \infty}x_{n}=x^{*}\]
				对于本题中的函数$ f(x) $,由$ f(x)=x $可解得不动点$ x^{*}=\dfrac{-p+\sqrt{p^{2}+4}}{2} $(舍去负根)\\
				由于$ f'(x)=-\dfrac{1}{(p+x)^{2}} $且$ p>1 $,则
				\[|f'(x^{*})|=\dfrac{4}{(p+\sqrt{p^{2}+4})^{2}}<1\]
				由引理,序列$ {x_{n}} $收敛,且$ x=\lim\limits_{n\to \infty}x_{n}=\dfrac{-p+\sqrt{p^{2}+4}}{2} $
			\end{proof}
		\item 解：由于$ a_{0}<0 $,则II中不等式中的$ \log a_{0} $无意义.\\
		步骤数n应满足
		\[n\geq\dfrac{\log(b_{0}-a_{0})-\log\epsilon-\log x}{\log2}-1 \]
		其中, $ x $为$ f(x)=0 $的精确解.\\
		在这种情况下，相对误差不是一个合适的度量，因为精确解$ x $可以等于0或趋向于0，从而导致$ n\to +\infty $.
	\end{enumerate}
	
	
\end{document}
